class Solution(object):
    def gcdOfStrings(self, str1, str2):
        """
        :type str1: str
        :type str2: str
        :rtype: str
        """
        n1 = len(str1)
        n2 = len(str2)
        def cmp(s, k, n):
            t = s[: k] * (n // k)
            return t == s
        for k in range(min(n1, n2), 0, -1):
            if n1 % k == 0 and n2 % k == 0:
                if cmp(str1, k, n1) and cmp(str2, k, n2) and str1[:k] == str2[:k]:
                    return str1[:k]
        return ''



